// package search 搜索相关算法
package search

const (
	notFoundRet = -1
)

// https://leetcode-cn.com/problems/binary-search/
// 二分查找
// 输入: 升序数组
// 时间复杂度: O(logn)
func Binary(nums []int, target int) int {
	if len(nums) == 0 {
		return notFoundRet
	}
	return binaryDeep(nums, 0, len(nums)-1, target)
}

func binaryDeep(nums []int, start, end, target int) int {
	mid := (start + end) / 2
	if nums[mid] == target {
		return mid
	}
	if start < mid {
		leftSearchRet := binaryDeep(nums, start, mid-1, target)
		if notFoundRet != leftSearchRet {
			return leftSearchRet
		}
	}
	// 注意：右分支和左分支没有任何关系
	if mid < end {
		return binaryDeep(nums, mid+1, end, target)
	}
	return notFoundRet
}
